import java.util.Stack;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.SET;
import edu.princeton.cs.algs4.TST;

public class BoggleSolver {
    private MyTST dic;
    private Node root;
    // Initializes the data structure using the given array of strings as the dictionary.
    // (You can assume each word in the dictionary contains only the uppercase letters A through Z.)
    public BoggleSolver(String[] dictionary)
    {
       dic=new MyTST();
       for(String word:dictionary)
       {
        dic.put(word);
       }
       root=dic.root;
    }

    // Returns the set of all valid words in the given Boggle board, as an Iterable.
    public Iterable<String> getAllValidWords(BoggleBoard board)
    {
       // 用这个队列存储在字典树中的单词 
      SET<String> boards=new SET<String>();

       // 遍历访问board单词
       // 用堆进行类似深度遍历的访问
       // 使用现成的字典树有点不是很好用了，最好自己实现一个，还是用TST的结构，不过这里是每往里访问一个，都要同步地在TST中进行检索
       // 检索失败就不用再访问了，而这样的同步进行也可以使得检索速度变快许多
       // 深度遍历board中的节点
       for(int i=0;i<board.rows();i++)
       {
         for(int j=0;j<board.cols();j++)
         {
            //如果有这个前缀
            Node x=zeroStepFind(root, board.getLetter(i, j));
            if(x!=null)
            {
               DFS(board,i,j,boards);
            }
         }
       }
       return boards;
    }

    //记录较复杂信息的点
    private class Point {
       public int i;
       public int j;
       public StringBuilder prefix;    // 表示当前的前缀
       public Node x;                  // 存储当前节点的位置
       public Point(int i,int j,StringBuilder prefix,Node x)
       {
         this.i=i;
         this.j=j;
         this.prefix=prefix;
         this.x=x;
       }
    }

    //仅用来记录位置信息
    private class smallPoint{
      public int i;
      public int j;
      public smallPoint(int i,int j)
      {
        this.i=i;
        this.j=j;
      }
    }

    // 检验并添加Point四周的点
    private void addAround(BoggleBoard board,Point Point,boolean[][] onEdge,SET<String> boards, Stack<Point> PointStack)
    {
      int rightBound=board.cols();  // 这里是列的数量，允许的最右侧点的列坐标是rightBound-1
      int bottomBound=board.rows(); // 同上
      int i=Point.i;
      int j=Point.j;
      // 左上存在点，并且左上方的点并不在路径上,并且左上方点字符加入后依旧在字典内可找到
      if(i>0&&j>0&&!onEdge[i-1][j-1])
      {
         addOne(board, Point, boards, PointStack, i-1, j-1);
      }

      // 上
      if(i>0&&!onEdge[i-1][j])
      {
        addOne(board, Point, boards, PointStack, i-1, j);
      }

      // 右上
      if(i>0&&j+1<=rightBound-1&&!onEdge[i-1][j+1])
      {
         addOne(board, Point, boards, PointStack, i-1, j+1);
      }

      // 左
      if(j>0&&!onEdge[i][j-1])
      {
         addOne(board, Point, boards, PointStack, i, j-1);
      }

      // 右
      if(j+1<=rightBound-1&&!onEdge[i][j+1])
      {
         addOne(board, Point, boards, PointStack, i, j+1);
      }

      // 左下
      if(i+1<=bottomBound-1&&j>0&&!onEdge[i+1][j-1])
      {
        addOne(board, Point, boards, PointStack, i+1, j-1);
      }

      // 下
      if(i+1<=bottomBound-1&&!onEdge[i+1][j])
      {
         addOne(board, Point, boards, PointStack, i+1, j);
      }

      // 右下
      if(i+1<=bottomBound-1&&j+1<=rightBound-1&&!onEdge[i+1][j+1])
      {
         addOne(board, Point, boards, PointStack, i+1, j+1);
      }
    }

    private void addOne(BoggleBoard board,Point Point,SET<String> boards, Stack<Point> PointStack,int i,int j)
    {
      Node now=Point.x;
      Node nextNode=onStepFind(now, board.getLetter(i, j));
      if(board.getLetter(i, j)=='Q')
      {
         nextNode=onStepFind(nextNode, 'U');
      }
      if(nextNode!=null)
      {
         StringBuilder newStringBuilder=new StringBuilder(Point.prefix);
         if(board.getLetter(i, j)=='Q')
         {
            newStringBuilder.append('Q');
            newStringBuilder.append('U');

         }
         else
         {
            newStringBuilder.append(board.getLetter(i, j));
         }
         Point newPoint=new Point(i, j, newStringBuilder, nextNode);
         String newString=newPoint.prefix.toString();
         // 如果这个点是标志一个单词结尾，并且这个单词长度至少为3，那么就把加入这个前缀的String加入boards
         if(nextNode.isend&&newString.length()>=3)
         { 
           boards.add(newString);
         }
         // 加入到PointStack中
         PointStack.push(newPoint);
      }
    }

    private Node onStepFind(Node x,char c)
    {
      return onStepFind(x, c, 1);
    }

    private Node zeroStepFind(Node x,char c)
    {
      return onStepFind(x, c, 0);
    }


    private Node onStepFind(Node x,char c,int d) // 树的一步查询,就是往深找一步，找到了继续，找不到就完蛋,从root开始找的时候是找0步
    {
      if (x == null) return null;
      else if (d == 1)               return onStepFind(x.mid, c, d-1);
      if      (c < x.c)              return onStepFind(x.left,  c,d);
      else if (c > x.c)              return onStepFind(x.right, c,d);
      else                           return x;
    }

    private void DFS(BoggleBoard board,int i,int j,SET<String> boards)
    {
      // 初始化
      Stack<Point> PointStack=new Stack<Point>();
      Stack<smallPoint> EdgeStack=new Stack<smallPoint>();
      boolean[][] onEdge=new boolean[board.rows()][board.cols()];
      for(int a=0;a<board.rows();a++)
      {
        for(int b=0;b<board.cols();b++)
        {
           onEdge[a][b]=false;
        }
      }
      //添加第一个
      StringBuilder newStringBuilder=new StringBuilder();
      if(board.getLetter(i, j)=='Q')
      {
         newStringBuilder.append('Q');
         newStringBuilder.append('U');

      }
      else
      {
         newStringBuilder.append(board.getLetter(i, j));
      }
      Node firstNode=zeroStepFind(dic.root, board.getLetter(i, j));
      if(board.getLetter(i, j)=='Q')
      {
         firstNode=onStepFind(firstNode, 'U');
      }
      PointStack.add(new Point(i, j,newStringBuilder,firstNode));  
      // 添加第一个
      // 通过循环访问完这个i j能有的所有点
      while (!PointStack.empty()) {
         onEdge[PointStack.peek().i][PointStack.peek().j]=true;
         EdgeStack.push(new smallPoint(PointStack.peek().i,PointStack.peek().j));
         //在addAround中进行判断是否具有满足条件的前缀，如果有则添加，如果没有则不进行添加
         addAround(board,PointStack.peek(),onEdge,boards,PointStack);
         // 达成条件则说明那条线上已经访问完了，我们可以进行回退的步骤了
         while(!PointStack.empty()&&PointStack.peek().i==EdgeStack.peek().i&&PointStack.peek().j==EdgeStack.peek().j)
         {
            onEdge[PointStack.peek().i][PointStack.peek().j]=false;
            EdgeStack.pop();
            PointStack.pop();
         }
      }
    }

    // Returns the score of the given word if it is in the dictionary, zero otherwise.
    // (You can assume the word contains only the uppercase letters A through Z.)
    public int scoreOf(String word)
    {
       if(dic.contains(word))
       {
         int length=word.length();
         int score=0;
         if(length==3||length==4)
         {
           score+=1;
         }
         else if(length==5)
         {
            score+=2;
         }
          else if(length==6)
         {
            score+=3;
         }
          else if(length==7)
         {
            score+=5;
         }
          else if(length>=8)
         {
            score+=11;
         }
         return score;
       }
       else
       {
         return 0;
       }
    }
    
    public static void main(String[] args) {
    In in = new In("dictionary-algs4.txt");
    String[] dictionary = in.readAllStrings();
    BoggleSolver solver = new BoggleSolver(dictionary);
    BoggleBoard board = new BoggleBoard("board-q.txt");
    int score = 0;
    for (String word : solver.getAllValidWords(board)) {
        StdOut.println(word);
        score += solver.scoreOf(word);
    }
    StdOut.println("Score = " + score);
}

}
